“Ningún lenguaje consistente puede contener los medios necesarios para definir su propia semántica” (Alfred Tarski)
Modelos Semánticos Formales de los Lenguajes de Programación
La semántica es el campo que estudia el significado de los lenguajes e incluye:
La definición de diferentes modelos semánticos formales y las relaciones entre ellos.
La relación entre los modelos semánticos formales y las teorías generalistas o universalistas, como teoría de modelos, teoría de dominios, teoría de categorías, teoría de la complejidad, álgebra universal, etc.
La búsqueda de un posible modelo semántico formal universal.
Un formalismo semántico ideal debe ser: no ambiguo, legible, modular, flexible y práctico.
La semántica formal de los lenguajes de programación trata de las posibles formas de representar el significado o interpretación de los lenguajes de programación, y tiene las utilidades siguientes:
Proporcionar una semántica precisa a un lenguaje de programación.
Clarificar el dominio de expresiones sobre el que se especifica la semántica.
Facilitar el aprendizaje de un lenguaje de programación mediante sus fundamentos conceptuales.
Para comprender cualquier programa escrito en el lenguaje.
Para establecer una conexión entre la sintaxis y la semántica.
Facilitar la implementación del lenguaje de programación mediante un intérprete o compilador. Incluso para generarlo de forma automática.
Facilitar la verificación formal de los programas.
Para demostrar que diferentes programas son o no equivalentes, pues la equivalencia está ligada a la semántica (el aspecto profundo del lenguaje) y no a la sintaxis (el aspecto superficial).
Los más importantes modelos semánticos formales para los lenguajes de programación son los siguientes:
Semántica denotacional
La semántica denotacional trata de formalizar los significados de las expresiones sintácticas de los lenguajes de programación mediante entidades matemáticas. Estas entidades matemáticas se denominan “denotaciones” o referentes de las expresiones sintácticas. Las denotaciones son, pues, entidades matemáticas que modelan los significados de las construcciones sintácticas del lenguaje [Strachey, 2000] [Scott & Strachey, 1971] [Stoy, 1977] [Scott, 1971].
La formalización se basa en tres etapas:
Primero se definen los dominios sintácticos: tipos de identificadores, de expresiones, de sentencias, etc.
En segundo lugar, se definen los dominios semánticos: conjuntos, funciones, estructuras algebraicas, etc. Hay modelos denotacionales que utilizan estructuras matemáticas más abstractas, como: espacios métricos, espacios topológicos, categorías, etc.
En tercer lugar, se definen las funciones que aplican dominios sintácticos en dominios semánticos.
Las características de la semántica denotacional son:
Es teórica y práctica. Inicialmente, la semántica denotacional fue concebida como un modelo teórico computacional. Sin embargo, pronto se hizo evidente su carácter práctico.
Rige el principio de composicionalidad: la denotación de una expresión del lenguaje se construye a partir de las denotaciones de sus componentes.
La semántica denotacional se puede considerar como la traducción o conversión de un sistema formal a otro, de un lenguaje fuente a un lenguaje objeto. Este enfoque es el que se ha hecho más popular con el paso de los años. El proceso de conversión pretende aclarar el significado o ganar un mayor conocimiento de la expresión sintáctica original. Se dice que hay “abstracción completa” (full abstraction) cuando hay una correspondencia una a una entre las expresiones de los dos formalismos.
La semántica denotacional también se denomina “semántica extensional” porque existe una relación visible entre los dos formalismos (el de entrada o sintáctico y el de salida, el denotacional matemático).
La semántica denotacional está inspirado en las ideas de Frege de “sentido” y “referencia”, donde “sentido” es la expresión formal original y la “referencia” es el objeto denotado por dicha expresión. Según esta concepción, dos versiones diferentes de (por ejemplo) la factorial de un número, tendrían distinto sentido y la misma denotación. Según la semántica denotacional, las dos versiones son equivalentes.
La semántica denotacional fue introducida inicialmente en 1967 por Chrisopher Strachey [2000] para formalizar la semántica del cálculo lambda. Posteriormente, Strachey y Dana Scott establecieron sus bases teóricas utilizando la teoría de dominios (Domain Theory) ideada por Scott, inspirándose precisamente en el cálculo lambda [Scott & Strachey, 1971]. El estudio de los tipos o categorías de dominios y sus propiedades es el objeto de la teoría de dominios. Los tipos de expresiones lingüísticas se interpretan como dominios.
La tendencia actual es contemplar la semántica denotacional desde el punto de vista de la teoría de modelos, y en donde la teoría de dominios es una rama de la teoría de modelos.
Semántica operacional
En la semántica operacional, la semántica de un programa se establece a través de una máquina abstracta que asocia a cada construcción sintáctica una secuencia de ejecución, es decir, describe el “cómo” se comportan los programas de manera explícita, precisa y detallada. Esta máquina abstracta debe disponer de primitivas operacionales de significado claro y preciso.
Dos programas que codifiquen (por ejemplo) la factorial de un número de manera diferente tienen distintas semánticas operacionales.
La semántica operacional también se denomina “semántica intensional” porque la semántica reside en las computaciones que se realizan a nivel interno, no visible, en la máquina abstracta.
En general, se considera que la semántica operacional complementa a la semántica denotacional, y que ambas semánticas son necesarias para una descripción completa de un lenguaje de programación. La semántica operacional para especificar el comportamiento de un programa. Y la semántica denotacional para razonar sobre los programas en términos de entidades abstractas.
El primer ejemplo de semántica operacional fue la definición de un intérprete para Lisp (escrito en el propio Lisp). Con Lisp es posible definir también la semántica operacional de cualquier lenguaje. Otros lenguajes definidos con semántica operacional son: Algol 60, PL/I y CSP.
A finales de los años 1960s apareció un lenguaje más elaborado para la definición de la semántica operacional llamada Universal Language Definer, que posteriormente se denominó VDL (Vienna Definition Language) [Wegner, 1972]. VDL se aplicó para definir la semántica del lenguaje PL/I, que fue el primer lenguaje que nació con una semántica definida, aunque no totalmente formal. Una versión posterior de VDL dió origen al VDM (Vienna Development Method), una metodología de desarrollo de software [Bjorner, 1978].
Es una forma de semántica operacional ideada por Gordon Plotkin [2004] que tiene las características siguientes:
Se centra en las transiciones entre los diferentes estados de un programa. Por eso, algunos autores prefieren usar la denominación “semántica de transiciones” (transition semantics) para resaltar esta característica.
Cada transición puede ser etiquetada con un mensaje dirigido al mundo exterior.
Las transiciones entre estados se definen mediante reglas de inferencia. Las reglas son relaciones binarias causa-efecto entre estados. Las reglas tienen la forma S→aS', que indica que el estado S puede evolucionar hacia el estado S' por la ejecución de la acción a. Hay una estructura algebraica (como sistema cerrado) que especifica las transiciones entre los diferentes estados. Un conjunto de reglas de inferencia constituye una SOS.
Los estados se definen mediante predicados, que también son relaciones binarias. La expresión SP indica que el predicado P se aplica en el estado S.
Hay también axiomas, que son reglas predefinidas.
Los axiomas y las reglas de inferencia son estructurales en el sentido de que toda transición compuesta se infiere de las transiciones entre sus componentes.
A menudo, las transiciones se definen en términos de transiciones elementales, que describen un comportamiento particularizado, de detalle.
La SOS se ha convertido en la forma más común para definir la semántica operacional y uno de los principales modelos semánticos formales por sus ventajas:
Es intuitivo, porque sus fundamentos son simples. Y al mismo tiempo es potente.
Es teórica y práctica.
Permite describir el comportamiento de un programa de manera observable.
Permite describir la semántica estática y la dinámica.
Permite describir clases de procesos.
Es aplicable a los procesos concurrentes. Generaliza el álgebra de procesos (process algebra). El álgebra de procesos es un formalismo algebraico utilizado para especificar sistemas concurrentes, así como los protocolos de comunicación y coordinación entre sistemas (sincronización, ejecución en serie o en paralelo, bloqueo, abstracción, etc.). Hay muchos tipos de álgebras de procesos (CCS, CSP, ASP, etc.).
Permite el desarrollo de herramientas de automatización a partir de una especificación SOS.
Facilita la verificación de compiladores.
Por su carácter genérico la SOS es aplicable a otros campos: modelado de sistemas biológicos (systems biology), comunicación y coordinación entre diferentes sistemas (middleware), seguridad de sistemas informáticos, verificación de hardware y software, etc.
Debido a su carácter general y a su difusión, la SOS se ha convertido en objeto de estudio por sí mismo, lo que ha conducido a diversas líneas de investigación que proponen diversos formatos de reglas y sus meta-teoremas asociados. Mediante una formalización de la SOS denominada “Transition System Specificacions” (TSS), se pueden deducir interesantes propiedades sobre la semántica operacional inducida. Las propiedades obtenidas por estos formatos de reglas abarcan desde su aplicación original a la semántica operacional hasta equivalencias en modelos de comportamiento en diversas áreas de aplicación.
Semántica axiomática
En la semántica axiomática, el significado de un lenguaje de programación se describe mediante axiomas de la lógica de predicados, es decir, como una teoría de los programas escritos en ese lenguaje en forma de axiomas, que son reglas de inferencia que caracterizan las diferentes construcciones del lenguaje. La forma general de las reglas es
{P} C {Q}
en donde C es una construcción sintáctica del lenguaje, P (precondición) y Q (postcondición) son aserciones (fórmulas del cálculo de predicados). Su significado es: Si se ejecuta C en un estado en el que se cumple la condición P, entonces producirá un resultado en el que se cumplirá la condición Q, que está determinada por P y C. Estas reglas establecen relaciones lógicas entre estados iniciales y finales. Hay que asociar al menos una regla para cada constructo C del lenguaje. Un ejemplo de regla es:
{x+1 = 3} y := x+1 {y = 3}
Como en toda teoría matemática, en la semántica axiomática hay:
Fórmulas (expresiones de la teoría).
Axiomas (fórmulas aceptadas inicialmente).
Reglas de inferencia (fórmulas para deducir nuevos teoremas a partir de los axiomas o de teoremas previos).
Una fórmula puede ser verdadera o falsa. Una fórmula verdadera es un teorema. El objeto de la teoría es definir qué fórmulas son teoremas.
Las construcciones sintácticas básicas (como la sentencia de asignación) se definen como axiomas.
Las construcciones sintácticas compuestas (como While) se definen mediante teoremas derivables de los axiomas, usando reglas de inferencia para la composición de programas.
La semántica axiomática se utiliza normalmente a posteriori, es decir, una vez definido el lenguaje, se estudia su semántica axiomática. Con este formalismo se facilita la demostración de propiedades de los programas y su verificación a posteriori (una vez desarrollados).
El modelo axiomático es más abstracto que el denotacional y, sin embargo, es más práctico. Es más abstracto porque no trata realmente del significado de un programa, sino sólo lo que puede demostrarse sobre él, sus propiedades. Y es más práctico porque permite formalizar las construcciones de un lenguaje.
El ejemplo canónico de la semántica axiomática es la lógica de Hoare [1969]. De hecho, las reglas utilizan las “ternas de Hoare” (P, C, Q).
Otro enfoque axiomático se basa en considerar los programas como demostraciones a partir de un cierto conjunto de axiomas. En la correspondencia Curry-Howard, los tipos de datos son teoremas y los programas son demostraciones de los teoremas. [ver Aplicaciones Lógica Correspondencia Curry-Howard.]
Semántica algebraica
Es una forma de semántica axiomática basada en leyes algebraicas del álgebra abstracta para formalizar la semántica. Los axiomas son especificaciones ecuacionales de las operaciones.
Se basa en identificar las diferentes clases de objetos y las diferentes operaciones que se pueden realizar sobre ellos. También se utilizan axiomas algebraicos para describir las características de dichos objetos.
La semántica algebraica permite especificar todo tipo de objetos, de bajo o alto nivel.
La metodología de la semántica algebraica se usa también para especificar tipos abstractos de datos (TADs). Es decir, las propiedades de los objetos de datos se definen mediante operaciones que acceden y manipulan los datos, sin tener en cuenta su implementación concreta.
La semántica algebraica surgió a finales de los años 1970s. Se basa en la teoría matemática del álgebra universal. Una especificación algebraica permite definir una estructura matemática de forma abstracta, junto con sus propiedades.
Existen varios lenguajes de especificación algebraica, como ASL, Larch, ACT One, Clear y OBJ. En el caso de OBJ, las sentencias son ecuaciones, las computaciones son demostraciones de teoremas, y los programas son teorías.
Semántica de acciones
En la semántica de acciones (action semantics), la semántica de un lenguaje se especifica mediante acciones, que expresan computaciones formalizadas a partir de unas acciones primitivas. Hay acciones derivadas, que son combinaciones de acciones primitivas.
La modelización de los diferentes tipos de acciones se realiza mediante facetas. Hay 5 tipos de facetas: básica, funcional, declarativa, imperativa y comunicativa. Cada faceta captura un determinado aspecto computacional.
La semántica de acciones fue propuesta por Peter Mosses [1992] con el fin de crear especificaciones semánticas legibles, modulares y prácticas.
Semántica categorial
Es una semántica que usa la teoría matemática de categorías como formalismo para especificar la semántica. La teoría de las categorías es una teoría unificadora de las estructuras matemáticas. Una aplicación de la teoría de categorías a la semántica de los lenguajes de programación ha sido realizada por Pierce [1991].
Gramáticas de atributos
Son gramáticas que extienden la gramática formal libre de contexto de un lenguaje para especificar la semántica [Knuth, 1968]. El proceso de añadir semántica a una descripción sintáctica se denomina”decoración”. La decoración se aplica a:
Símbolo X (terminal o no terminal).
Se le asocia un conjunto de atributos A(X), que reflejan las propiedades del símbolo. Se usa la notación X.a para designar el atributo a del símbolo X.
Producción P.
Se le asocia un conjunto de condiciones semánticas CS(P) y un conjunto de funciones semánticas FS(P). CS(P) restringe los valores de los atributos de los símbolos que aparecen en P. FS(P) define un atributo en términos de otros atributos de símbolos que aparecen en P.
Los atributos se clasifican en:
Intrínsecos (o predefinidos).
Sintetizados (se calculan cuando el símbolo aparece en el lado izquierdo de la producción).
Heredados (se calculan cuando el símbolo aparece en el lado derecho de la producción).
Este modelo semántico es un marco general para especificar la semántica, más que un método
completamente definido, pues está abierto a la elección de los atributos y las reglas.
Las gramáticas de atributos se aplican a gran variedad de campos, entre ellos: especificación formal (sintaxis y semántica) de los lenguajes de programación, generación automática de compiladores, definición formal de entornos de programación, programación lógica, teoría de la complejidad, representación del conocimiento, reconocimiento del lenguaje natural y reconocimiento de patrones.
Una gramática de atributos se puede considerar como una semántica denotacional en donde el lenguaje original es enriquecido con atributos o anotaciones.
MENTAL, un Modelo Semántico General de los Lenguajes de Programación
En los últimos años ha habido una enorme proliferación de modelos semánticos formales de los lenguajes de programación. Todo este panorama genera confusión, produce perplejidad y nos conduce a plantearnos: 1) en primer lugar, sobre la verdadera naturaleza de la semántica; 2) la cuestión de la posibilidad de la existencia de un modelo formal unificado y simple del que surjan todos los modelos particulares, pues se sospecha que esta diversidad es solo aparente, y que tras esta diversidad de modelos se esconde algo fundamentalmente simple.
Mientras que para la especificación de la sintaxis de un lenguaje de programación se utiliza universalmente la notación estándar BNF o BNFE (BNF extendido), para la especificación de la semántica existen diferentes modelos formales, pero ninguno de estos modelos se ha convertido en estándar, pues ninguno ha alcanzado ni popularidad ni un alto grado de utilización, porque ninguno se ha considerado completo. Se puede decir que la especificación de la semántica formal ha fracasado. Y ha fracasado por una razón muy simple: porque la semántica de un lenguaje es inexpresable desde fuera del lenguaje y desde dentro (el lenguaje no puede expresar su propia semántica).
El significado no es algo externo, representable y objetivable. El significado es algo interno (mental), subjetivo y no representable. Sin embargo, el significado se fundamenta en arquetipos comunes al mundo interno y externo, por lo que es compartido por todos los seres humanos. Lo externo nos conecta con lo interno. Esa conexión es la conciencia. El significado “no está en la cabeza” sino en otra dimensión de la realidad, en la dimensión mental y en la conciencia. El significado es un fenómeno mental, de conciencia, y los significados de las expresiones lingüísticas se corresponden con las representaciones a nivel interno.
A la semántica de un lenguaje de programación se la ha relacionado con entidades matemáticas abstractas, con lo operativo, con el álgebra, con la lógica, con la demostración, etc. La semántica está muy relacionada con el tipo, con la categoría, con lo intensivo, pues todo ente particular debe verse como una instancia de algo general o profundo. Por lo tanto, la semántica no se puede formalizar. La única forma de formalizar la semántica es ligarla a la sintaxis como manifestación de los arquetipos primarios. Entonces se produce la integración de todos los formalismos semánticos anteriores en un modelo formal universal o unificado con el que se pueden especificar todos los modelos formales particulares.
Siempre se ha considerado que la semántica de un lenguaje de programación es más difícil de formalizar que la sintaxis. En el caso de MENTAL, ambos aspectos se igualan porque van unidos. Como la semántica no se puede expresar, en general para especificar la semántica de un lenguaje de programación, es necesario usar descripciones informales en lenguaje natural y ejemplos como manifestaciones superficiales de la semántica. Esto también se hace en MENTAL, pero como las primitivas semánticas son simples y la sintaxis también, las descripciones se reducen al máximo.
En MENTAL, la epistemología y la ontología van unidas. Por eso es el lenguaje de la conciencia.
MENTAL es un modelo semántico formal unificado que, por su alto nivel de abstracción, integra e interrelaciona todos los modelos semánticos formales anteriormente mencionados. Ocurre lo mismo que con los paradigmas de programación, pues MENTAL ofrece un paradigma universal que permite especificar todos los paradigmas particulares.
Denotacional.
El problema de la semántica denotacional es que el significado está limitado a entidades matemáticas. Pero esto implica varios problemas: 1) la matemática no está formalizada, carece de lenguaje formal; 2) no se sabe con exactitud cuales son los tipos de entidades matemáticas fundamentales y sus modos combinatorios; 3) la matemática no contempla el aspecto operacional; 4) en informática hay conceptos que no pueden considerarse estrictamente matemáticos, como asignación, concurrencia, reglas, objetos, agentes, aspectos, etc.
MENTAL trasciende la matemática. Sus primitivas están en un nivel de abstracción superior. No no necesita un proceso de conversión de expresiones, pues sintaxis y semántica están unidas. El significado de las expresiones está ligado a su sintaxis. Significado y denotación son dos caras de la misma moneda. Cada expresión es una manifestación de una primitiva o de una combinación de primitivas.
Operacional.
Los problemas de la semántica operacional son: 1) solo contempla el aspecto operativo o computacional; 2) no hay una máquina abstracta estándar.
En MENTAL, toda expresión, sin excepción, tiene una interpretación operacional, que corresponde al proceso de evaluación. El resultado de la evaluación puede considerarse su denotación, que tiene también su correspondiente significado. Además, MENTAL es un lenguaje descriptivo y operativo.
Semántica operacional estructurada (SOS).
Está orientado solo a reglas operativas.
MENTAL, por su carácter general, como SOS, debe ser también objeto de estudio por sí mismo, independientemente de sus aplicaciones particulares. Hay muchas leyes aún pendientes de descubrir, las leyes que relacionan las primitivas.
Axiomática.
El problema de semántica axiomática es que se trata de un enfoque exclusivamente lógico. La tradición algebraica (o paradigma algebraico), que empezó con Boole, descarta el significado y solo considera la denotación. La justificación de esta mutilación de la lógica es que funciona, pero solo a nivel formal o superficial, ignorando el aspecto profundo, la semántica, el significado, lo conceptual.
MENTAL utiliza axiomas, que son relaciones, definiciones o leyes generales establecidas a priori entre las primitivas. La demostración es una construcción a partir de las instancias de los axiomas semánticos, que son recursos inagotables de instancias.
Algebraica.
MENTAL es un álgebra general o universal, pues permite combinar todo tipo de expresiones.
De acciones
MENTAL es una semántica de acciones porque se fundamenta en unas primitivas semánticas universales. Estas primitivas trascienden lo puramente operativo. Las combinaciones de acciones primitivas se realizan mediante las propias primitivas. La semántica lexical es igual a la semántica estructural.
Las facetas en MENTAL son las diferentes formas o patrones primarios de combinar las primitivas para crear todo tipo de expresiones (funciones, reglas, objetos, etc.).
Gramáticas de atributos.
Las gramáticas de atributos tienen varios problemas: 1) separan la sintaxis de la semántica, no existiendo correspondencia directa entre cada construcción sintáctica y su semántica; 2) se da prioridad a la sintaxis, que es la base de la definición formal; 3) la semántica es un añadido a la sintaxis; 4) no contempla estructuras globales.
En definitiva, por su supremo nivel de abstracción, MENTAL proporciona una semántica natural y universal que permite formalizar todos los modelos semánticos descritos. MENTAL es la semántica formal de todos los lenguajes de programación y el formalismo semántico de todo programa. El modelo de MENTAL trasciende la informática y la matemática. Es un modelo semántico universal en el que sintaxis y semántica van unidas, que es una característica de la conciencia.
Adenda
Teoría de dominios
La teoría de dominios es una rama de la matemática que estudia clases especiales de conjuntos parcialmente ordenados (partially ordered sets, posets) denominados “dominios”.
Un poset es un conjunto en el que se ha definido una relación de orden parcial (≤) binaria entre sus elementos que cumple las propiedades:
x≤x (reflexividad)
Si x≤y e y≤z, entonces x≤z (transitividad)
Si x≤y e y≤x, entonces x=y (antisimetría)
La relación de orden es total cuando para todo par de elementos (x, y) del conjunto, se cumple que x≤y o y≤x.
Los números reales son un ejemplo de poset con una relación de orden total.
Un retículo (lattice) es un poset en el que hay un elemento supremo y un elemento ínfimo. Por ejemplo, los subconjuntos de un conjunto dado ordenados por inclusión. El supremo es la unión de todos, y el ínfimo la intersección de todos.
A finales de los años 1960s, Dana Scott −un alumno de Church− formalizó, con la ayuda del cálculo lambda, unas estructuras matemáticas que denominó “dominios”, que servían para representar tipos funcionales, en lugar de los tipos de los conjuntos tradicionales [Abramsky & Jung, 1994]. Su motivación principal fue formalizar la semántica del cálculo lambda mediante la semántica denotacional.
La teoría de dominios se considera una teoría matemática de la computación, pues se aplica principalmente para especificar la semántica denotacional y los lenguajes de programación funcional.
La teoría de dominios tiene estrechas relaciones con la topología, pues el modelo denotacional utilizado por Scott [1976], se basa en un espacio topológico “aplicativo” en el que cada elemento de dicho espacio se interpreta como una función o como un argumento de una función. Estos dos aspectos definen precisamente la relación de orden. El conjunto de estas funciones, junto con esta relación de orden parcial, es un dominio. Hay dominios constituidos por funciones que pueden aplicarse a sí mismas. Los espacios de aplicación aparecen en su forma más pura en el cálculo lambda, pues una expresión lambda se puede utilizar como función o como argumento de otra expresión lambda.
La teoría de dominios formaliza y fundamenta las funciones recursivas, la información continua y la infinitesimal. El modelo formaliza las ideas intuitivas de aproximación y convergencia. La computación es modelada aplicando funciones monótonas recursivamente sobre elementos del dominio para refinar un resultado.
Dentro de un dominio hay una jerarquía de información o conocimiento. Cuanto más alto está una función en la jerarquía, más específica es y más información contiene. Los elementos inferiores representan información incompleta o resultados intermedios.
Scott formalizó, mediante la teoría de dominios, la noción de “información parcial o incompleta” para representar computaciones que nunca terminan con un resultado final. Esto lo modeló asociando a cada dominio de computación un elemento adicional que representa un resultado indefinido. Dentro del dominio, que es parcialmente ordenado, el “resultado indefinido” es el de menor nivel de la jerarquía.
Bibliografía
Abramsky, Samson.; Jung, Achim. Domain Theory. Handbook of Logic in Computation Science. Oxford University Press, 1994. Disponible en Internet.
Bjorner, Dines; Jones, Cliff B. (Eds.). The Vienna Development Method: The Meta-Language. Lecture Notes in Computer Science, 61. New York: Springer-Verlag. 1978.
Goguen, Joseph A.; Malcolm, Grant. Algebraic Semantics of Imperative Programs. The MIT Press, 1996.
Gunter, Carl. Semantics of Programming Languages. MIT Press, 1992.
Hoare, C.A.R. An axiomatic Basis for Computer Programming. Comm. ACM, 10:576-583, 1969.
Knuth, D.E. Semantics of Context Free Languages. Mathematical Systems Theory, pp. 127-145, 2 (1968) 2.
Liang, Sheng; Hudak, Paul ; Jones, Mark P. Monad transformers and modular interpreters. In 22nd ACM Symposium on Principles of Programming Languages, San Francisco, CA. ACM, January 1995.
Liang, Sheng; Hudak, Paul. Modular denotational semantics for compiler construction. In Programming Languages and Systems – ESOP’96, Proc. 6th European Symposium on Programming, Linköping, vol. 1058 of Lecture Notes in Computer Science, pp. 219–234. Springer-Verlag, 1996.
Link, Godehard. Algebraic Semantics in Language and Philosophy. Center for the Study of Language and Information, 1997.
Mosses, Peter D. Action Semantics. Cambridge University Press, 1992.
Pierce, Benjamin C. Basic Category Theory for Computer Scientists. Cambridge, MA: MIT Press, 1991.
Plotkin, Gordon D. A Structural Approach to Operational Semantics. Journal of Logic and Algebraic Programming, vol. 60, pp. 17-139, 2004. Disponible en Internet.
Reynolds, John C. Theories of Programming Languages. Cambridge University Press, 1998.
Scott, D.S. Outline of a mathematical theory of computation. Report PRG-2, Programming Research Group, Univ. Of Oxford, 1971.
Scott, D.S. Data Types as Lattices. SIAM Journal on Computing 5:522-587, 1976. Disponible en Internet.
Scott, D.S.; Strachey, C. Towards a mathematical semantics for computer languages. Computers and Automata, Microwave Research Institute Symposia 21, 1971, pp. 19-46.
Stoy, J.E. Denotational Semantics. The Scott-Strachey Approach to Programming Language Theory. Cambridge, MA: M.I.T. Press, 1977.
Strachey, C. Fundamental Concepts in Programming Languages. Higher Order and Symbolic Computation, vol. 13, April 2000.
Tennent, Robert D. Semantics of Programming Languages. Prentice-Hall, 1991.
Turi, Daniele; Plotkin, Gordon. Towards a Mathematical Operational Semantics. Internet.
Vogt, H.H.; Swieerstra, S.D.; Kniper, M.F. Higher order attribute grammars. In Proceedings of the ACM SIGPLAN’89 Conference on Programming Language Design and Implementation, pp. 131-145, Portland, Oregon, June 21-23, 1989.
Wegner, P. The Vienna Definition Language. ACM Comp Surveys 4(1):5-63, Mar 1972.
Winskel, Glynn. The Formal Semantics of Programming Languages. An Introduction. MIT Press, 1993.
